Fast-growing hierarchy

큰 수들의 크기를 비교할 때 쓰이는 계층구조. FGH는 커지면 커질수록 뭔가가 더 붙는 다른 큰 수 함수들과는 다르게 간결하고 매우 강력하여 큰 수들을 비교할때 요긴하게 쓰인다.

이해를 돕기 위해서 정의를 풀어서 다시 쓰면 다음과 같다.

각 단계는 하나의 함수를 가리킨다. 정의 (2)에 의해서 같은 단계의 함수에 더 큰 수를 집어넣는 것보다 단계를 높이는 것이 결과값을 훨씬 크게 만든다. 서수가 조금만 커져도 우주 원자 수 정도는 가뿐히 넘는다. 대신 1, 2를 대입한다면 매우 큰 가산서수를 가져와도 값이 3을 넘지 못하는 경우가 있기 때문에 높은 단계의 크기를 체감하고 싶을 때에는 보통 $n$에 3을 대입하는 경우가 많다.

정의에 의해 서수 0에 해당하는 함수는 '다음 수'라는 연산이다. $f_0(n) = n+1,\ f_0(100)=101$

서수 1에 해당하는 함수는 '다음 수'를 $n$번 반복한 것이므로 $n+n=2n$이다. $f_1(n) = 2n,\ f_1(100)=200$

서수 2에 해당하는 함수는 2배하기를 $n$번 반복하는 것이므로[1] $2 \times 2 \times ... \times 2 \times n = n \times 2^n$이다. $f_2(n) = n \times 2^n,\ f_2(100)=100 \times 2^{100} \sim 1.267$구

서수 3에 해당하는 함수는 $n \times 2^n, (n \times 2^n) \times 2^{(n \times 2^n)}, ...$ 이런식으로 $n$번 합성하는 것이다.[2]줄임표를 사용하지 않고 정확하게 나타내기는 힘들고 근삿값은 $(2^n)^{(2^n)^{...^{(2^n)}}}$으로 $2^n \uparrow \uparrow n$과 같다. $\uparrow \uparrow$의 의미는 커누스 윗화살표 표기법 참고.

서수 4에 해당하는 함수는 위의 함수를 $n$번 합성한 것이므로 근삿값으로 $2 \uparrow \uparrow 2 \uparrow \uparrow.. \uparrow \uparrow n$이고 이것은 $2 \uparrow \uparrow \uparrow n$보다 크다.

서수 5에 해당하는 함수는 위의 함수를 $n$번 합성한 것이므로 근삿값으로 $2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow ... \uparrow \uparrow \uparrow n$이고 이것은 $2 \uparrow \uparrow \uparrow \uparrow n$보다 크다. 즉 유한 서수 $a+1$에 대한 함수는 대략 크누스의 윗 화살표 표기법으로 화살표가 $a$개 있는 것과 비슷하다. (화살표 앞뒤에 붙는 수의 크기는 2 이상이기만 하면 크게 중요하지 않다.)

그러면 윗화살표 표기법만 가지고 모든 단계를 근사할 수 있을까? 아니다. 아직 정의 (3)은 쓰지도 않았다. 여기서 가장 작은 극서수인 $\omega$가 등장한다.

서수 $\omega$에 해당하는 함수는 정의(3)에 의해 $\omega$에 n을 대입해서 n단계 함수가 된다. $\omega$의 fundamental sequence의 $n$번째 항은 $n$이기 때문이다. 즉 $f_{\omega}(100)=f_{100}(100)$이다.

서수 $\omega+1$ 에 해당하는 함수 $f_{\omega+1}(n)$은 절대 $f_{n+1}(n)$가 아니다. $\omega+1$은 극서수가 아니기 때문에 정의 (2)에 의하여 $f_{\omega+1}(n)$은 $f_{\omega}(n)$를 $n$번 중첩하는 것인데, $f_{100}(100)$을 계산해서 나오는 엄청 큰 수를 $A$라고 하면 서수 $A$에 해당하는 함수인 $f_A(A)$를 계산해야 하고 그 결과를 또 단계에 넣고 하는 것을 100번 반복해야 $f_{\omega+1}(100)$이 나온다.

$f_{\omega2}(n)$는 $\omega2$가 서수의 수열 $\omega+1, \omega+2, \cdots$로 정의되기 때문에, 정의 (3)에 의해 $f_{\omega+n}(n)$와 같다.[3] 이를 반복하면 $f_{\omega (m+1)}(n)$는 $f_{\omega m+n}$가 된다.

$f_{\omega^2}(n)$는 같은 원리로 정의 (3)을 사용하여 $f_{\omega n}(n)$가 되고, $f_{\omega^\omega}(n)$는 $f_{\omega^n}(n)$이 된다.

이제 몇몇 큰 수들을 이 표기법으로 어떻게 나타낼 수 있는지 알아보자.

구골의 경우, 약간의 계산을 거치면 $f_{2}(323)=323\times2^{323}\lt10^{100}\lt324\times2^{324}=f_{2}(324)$임을 알 수 있다. 하지만 서수 3에 대한 함수로는 $f_{3}(2)=2048\lt10^{100}\lt f_{3}(3)$이 되어, 비교하는 의미가 없어진다.

스큐스 수의 경우, 대략 $f_3(4)\lt e^{e^{e^{79}}}\lt f_3(5)\lt f_4(2)$이다.

그레이엄 수의 경우, 윗 화살표가 $g_{63}$개이므로 유한 서수로 나타내기에는 너무 크다. 대신, $g_{1}=3\uparrow\uparrow\uparrow\uparrow3\lt f_{64}(64)$에서 시작하여 $g_{2}\lt f_{f_{64}(64)}(f_{64}(64))$를 보이고, 이 과정을 64번 반복하면 $g_{64}\lt f_{\omega+1}(64)$인 것을 알 수 있다.[4]

이처럼 큰 수들은 그 크기에 "대응"하는 서수를 가지는 경우가 많기 때문에, 큰 수들의 크기를 편리하게 비교할 수 있다.

그리스 문자는 무한하지 않기 때문에, 다음 단계로 나아가기 위해 앞의 극서수들을 일반화한 베블런 함수 $\varphi(n)$을 사용한다.

1. $\varphi_0(a)=\omega^a$
2. 서수 $\alpha$에 대해, $\varphi_\alpha(0)[n]=\varphi^n_{\alpha-1}(0)$
3. $\varphi_\alpha(m)[n]=\varphi^n_{\alpha-1}(\varphi_\alpha(m-1)+1)$
4. $\alpha$가 극서수라면, $\varphi_\alpha(0)[n]=\varphi_n(0)$
5. $\varphi_\alpha(m)[n]=\varphi_n(\varphi_\alpha(m-1)+1)$

이 문서에서는 서수 붕괴 함수가 어떻게 커지는지만 중점적으로 다룬다. 자세한 원리는 서수(수학)/큰 가산서수 문서의 5번째 문단 참고.

더 나아가

를 생각 할 수 있고, 이 밑첨자를 큰 베블런 서수(Large Veblen Ordinal)라고 한다.

$\Gamma_0$에 대해, $f_{\Gamma_0}(2)$를 구해보자. 이 서수는 $\{1, \varphi_1(0), \varphi_{ \varphi_1(0)}(0), \varphi_{ \varphi_{ \varphi_1(0)}(0)}(0), \cdots\}$의 극서수이므로 이것은 $f_{\varphi_1(0)}(2)=f_{\epsilon_0}(2)$과 같다. $\epsilon_0$은 $\{1, \omega, \omega^\omega, \omega^{\omega^\omega} \cdots\}$의 극서수라서, 이것은 $f_{\omega}(2)$와 같고, $f_{\omega}(2)=f_{2}(2)=8$이 된다. 이렇듯 많은 극서수를 정의하는 수열이 1부터 시작하므로, 2 이하의 수는 계산이 너무 쉽게 끝나게 된다. 만약 $\Gamma_0+1$과 같이 극서수가 아니라 따름서수라면 $f_{\Gamma_0+1}(2)=f_{\Gamma_0}(f_{\Gamma_0}(2))=f_{\Gamma_0}(8)$처럼 재귀를 통해 값이 3 이상이 되어 그나마 낫다.

나아가서 1을 넣으면 서수가 무엇이든 결과값이 2로 고정된다. fundamental sequence가 1로 시작하는 극서수[8]인 $\alpha$에 대해 $f_\alpha(1)$를 계산하면 $f_1(1)=f_0(1)=2$가 된다. $\alpha$가 따름서수라도 한번만 재귀하게 되어 $f_{\alpha}(1)=f_{\alpha-1}(1)$이므로 재귀를 통해 값을 늘릴 수도 없다.